#include<stdio.h>
#include<stdlib.h>
struct node{
       int data;
       struct node *next;
       };

struct node *append(struct node *);
struct node *extend(struct node *);
struct node *insert(struct node *);
struct node *remove_list(struct node *);
struct node *pop(struct node *,int *);
void index_list(struct node *,int *);
void count(struct node *,int *);
struct node *sort(struct node *,int);
struct node *swap(struct node *,struct node *,struct node *,int);
void display(struct node *); 
struct node *set(struct node *,struct node *,int);    
struct node * data(struct node *,int);

int main(void)
{
  int ch=1,x,i,*rt;
  struct node *p;
  p=NULL;
  rt=(int *)malloc(sizeof(int));
  *rt=0;
  while(ch!=4)
  {
    system("cls");
    printf(">>>Main Menu<<<\n1.Create a list\n2.Implement a function\n3.Display the list\n4.Exit\nEnter your choice:");
    scanf("%d",&ch);
    if(ch==1)
    {  printf("1 list loaded");
       getch();
    }
    else if(ch==2)
    {
      while(ch!=11)
      {
        system("cls");
        printf(">>>Function Menu<<<\n1.list.append(x)\n2.list.extend(L)\n3.list.insert(i,x)\n4.list.remove(x)\n5.list.pop([i])\n6.list.index(x)\n7.list.count(x)\n8.list.sort()\n9.list.reverse()\n10.list.display()\n11.Return to previous menu\nEnter your choice:");
        scanf("%d",&ch);
        switch(ch)
        {
          case 1:p=append(p);
               break;
          case 2:p=extend(p);
               break;
          case 3:p=insert(p);
               break;
          case 4:p=remove_list(p);
               break;
          case 5:p=pop(p,rt);
               break;
          case 6:index_list(p,rt);
            break;
          case 7:count(p,rt);
            break;
          case 8:p=sort(p,0);
               break;
          case 9:p=sort(p,1);
               break;
          case 10:display(p);break;
          case 11:break;
          default:printf("Invalid input\n");
        }    
      }
    }
    else if(ch==3)
         display(p);
  }
  return 0;
}
int size(struct node *p)
{
    int i=0;
    while(p!=NULL)
    {
      i++;
      p=p->next;
    }
    return i;
}
void display(struct node *p)
{
     struct node *q;
     printf("[");
     q=p;
     while(q!=NULL)
     {
       printf("%d,",q->data);
       q=q->next;
     }
     printf("\b]\n");
     getch();
}
struct node * extend(struct node *p)
{
     int a[10],i,m;
     struct node *q=p,*temp;
     printf("Enter number of elements in list2:");
     scanf("%d",&m);
     for(i=0;i<m;i++)
     {
       printf("Enter element %d:",i+1);
       scanf("%d",&a[i]);
     }
     while(q->next!=NULL)
       q=q->next;
     for(i=0;i<m;i++)
     {
       temp=(struct node *)malloc(sizeof(struct node));
       temp->data=a[i];
       temp->next=NULL;
       q->next=temp;
       q=q->next;
     }
     return p;
}
struct node* insert(struct node *p)
{
     int i,x,j;
     struct node *q=p,*temp;
     printf("Enter i:");
     scanf("%d",&i);
     printf("Enter x:");
     scanf("%d",&x);
     j=size(p);
     if((i>j+1) || (i<=0))
     {
       printf("Index out of range.\n");
       getch();
       return p;
     }
     q=p;
     if(i==1)
     {
       temp=(struct node*)malloc(sizeof(struct node));
       temp->data=x;
       temp->next=q;
       return temp;
     }
     j=1;
     while(j!=i-1)
     {
       q=q->next;
       j++;
     }
     temp=(struct node*)malloc(sizeof(struct node));
     temp->data=x;
     temp->next=q->next;
     q->next=temp;
     return p;
}
struct node * remove_list(struct node *p)
{
     int i=0,data,temp=0;
     struct node *q=p,*r;
     printf("Enter data:");
     scanf("%d",&data);
     while(q!=NULL)
     {

       if(q->data==data)
       {
         temp=1;
         break;
       }
       q=q->next;
     }
     if(temp==0)
     {
       printf("No such element in the list.\n");
       getch();
       return p;
     }
     q=p;
     while(q->next!=NULL)
     {
       if(data==q->next->data)
       {
         r=q->next;
         q->next=r->next;
         free(r);
         return p;
       }
       q=q->next;
     }  
}
struct node * pop(struct node *p,int *rt)
{
     int i,j=0,temp=0,n;
     struct node *q=p,*r;
     printf("Enter i(-1 for null):");
     scanf("%d",&i);
     n=size(p);
     if(n==0)
     {
       printf("List is empty.\n");
       getch();
       return p;
     }
     if((i<-1) || (i>n-1))
     {
       printf("Invalid input\n");
       getch();
       return p;
     }
     else if(i==-1 || i==n-1)
     {
       if(n==1)
       {
         *rt=q->data;
         printf("%d returned",*rt);
         free(q);
         return NULL;
       }
       r=p;
       while(q->next!=NULL)
         q=q->next;
       while(r->next!=q)
         r=r->next;
       r->next=NULL;
       *rt=q->data;
       printf("%d returned",*rt);
       getch();
       free(q);
       return p;
     }
     else if(i>=0 && i<n-1)
     {
       j=0;
       while(q->next!=NULL && j<n)
       {
         if(j==i)
           break;          
         q=q->next;
         j++;
       }
       r=p;
       if(r==q)
       {
         r=r->next;
         *rt=q->data;
         free(q);
         printf("%d returned\n",*rt);
         getch();
         return r;
       }
       while(r->next!=q)
         r=r->next;
       r->next=q->next;
       *rt=q->data;
       printf("%d returned\n",*rt);
       free(q);
       getch();
       return p;
     }
}
void index_list(struct node *p,int *rt)
{
     int data,i=0;
     struct node *q=p;
     printf("Enter data:");
     scanf("%d",&data);
     while(q!=NULL)
     {  
       if(q->data==data)
         break;
       i++;
       q=q->next;
     }
     if(q!=NULL)
     {
       *rt=i;
       printf("%d returned",*rt);
     }
     else
       printf("Data not present");
     getch();
}
void count(struct node *p,int *rt)
{
  int c=0,data,i;
  struct node *q=p;
  printf("Enter data:");
  scanf("%d",&data);
  while(q!=NULL)
  { if(q->data==data)
      c++;
    q=q->next;
  }
  *rt=c;
  printf("%d returned",*rt);
  getch();
}
struct node * data(struct node *p,int i)
{
    int j=0;
    while(p!=NULL)
    {
      if(j==i)
        break;
      j++;
      p=p->next;
    }
    return p;
}
struct node *set(struct node *p,struct node *q,int mode)
{
       if(mode==0)
         while(p!=NULL)
         {
           if(p->next==q)
             break;
           p=p->next;
         }
       else if(mode==1)
         while(p!=NULL)
         {
           if(q->next==p)
             break;
           p=p->next;
         }
       return p;
         
}
struct node *swap(struct node *p,struct node *u,struct node *v,int diff)
{
       struct node *A=p,*B,*C,*D;
       if(diff!=1)
         if(A==u)
         {
           B=set(p,u,1);
           C=set(p,v,0);
           D=set(p,v,1);
           p=v;
           v->next=B;
           C->next=u;
           u->next=D;
           return p;
         }          
         else
         {
           A=set(p,u,0);
           B=set(p,u,1);
           C=set(p,v,0);
           D=set(p,v,1);
           A->next=C->next;
           v->next=B;
           C->next=u;
           u->next=D;
           return p;
         }
       else
         if(A==u)
         {
           D=set(p,v,1);
           p=v;
           v->next=u;
           u->next=D;
           return p;
         }
         else
         {
           A=set(p,u,0);
           D=set(p,v,1);
           A->next=v;
           v->next=u;
           u->next=D;
           return p;
         }
}
struct node * sort(struct node *p,int a)
{
     int i,j,temp,n;
     struct node *u,*v;
     n=size(p);
     for(i=0;i<n;i++)
       for(j=0;j<=i;j++)
       {
         u=data(p,j);
         v=data(p,i);  
         if((u->data)>(v->data) && a==0)
           p=swap(p,u,v,i-j);
         else if((u->data)<(v->data) && a==1)
           p=swap(p,u,v,i-j);
       }
     printf("Array sorted\n");
     getch();
     return p;
}
struct node * append(struct node *p)
{
     struct node *temp,*q;
     int data;
     temp=(struct node *)malloc(sizeof(struct node));
     temp->next=NULL;
     printf("Enter data:");
     scanf("%d",&data);
     temp->data=data;
     q=p;
     if(q==NULL)
     {
       p=temp;
       return p;
     }
     while(q->next!=NULL)
       q=q->next;
     q->next=temp;
     return p;
}
